package com.LeetCode.dp.String;

import org.junit.Test;

/**
 * 最长公共子序列
 */
public class LCS {
    public int longestCommonSubsequence(String a, String b) {
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                if(a.charAt(i-1) == b.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }

    @Test
    public void test(){
        String a = "abcde";
        String b = "ace";
        System.out.println(longestCommonSubsequence(a,b));
    }
}
